package leetcode;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * @program: datastructureandalogorithm
 * @description:
 * @author: hmx
 * @create: 2021-12-16 14:16
 **/
public class LeetCode207 {

    public boolean canFinish(int numCourses, int[][] prerequisites) {
        //图
        List<Integer>[] g = new List[numCourses];
        for (int i = 0; i < numCourses; i++) {
            g[i] = new ArrayList<>();
        }

        //入度表
        int[] inDeg = new int[numCourses];
        //向图中添加边
        for (int[] prerequisite : prerequisites) {
            g[prerequisite[1]].add(prerequisite[0]);
            ++inDeg[prerequisite[0]];
        }

        //队列维护入度为0的顶点
        Queue<Integer> q = new LinkedList<>();
        //把所有入度为0的点加入到队列中
        for (int i = 0; i < numCourses; i++) {
            if(inDeg[i] == 0) {
                q.offer(i);
            }
        }

        //存放拓扑排序后的点
        List<Integer> res = new ArrayList<>();
        while (!q.isEmpty()) {
            int x = q.poll();
            res.add(x);
            for (int y : g[x]) {
                if (--inDeg[y] == 0) {
                    q.offer(y);
                }
            }
        }
        return res.size() == numCourses;
    }

}
